package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;

/**
 * 使用归并排序方法排序单向链表
 * @author zifangsky
 *
 */
public class Problem_017_SortLinkedList {

	/**
	 * 遍历一个单链表的data
	 * 
	 * @时间复杂度 O(n)
	 * @空间复杂度 O(1)
	 * @param headNode 表头节点
	 */
	public void print(SinglyNode<Integer> headNode){
		while(headNode != null){
			System.out.print(headNode.getData() + " ");
			headNode = headNode.getNext();
		}
		System.out.println();
	}
	
	/**
	 * 返回单链表的中间节点
	 * @时间复杂度 O(n/2) = O(n)
	 * @param headNode
	 * @return
	 */
	public SinglyNode<Integer> findMiddle(SinglyNode<Integer> headNode){
		if(headNode != null){
			SinglyNode<Integer> slow = headNode,fast = headNode;
			
			while(fast != null && fast.getNext() != null && fast.getNext().getNext() != null){
				slow = slow.getNext();
				fast = fast.getNext().getNext();
			}
			return slow;
		}else{
			return null;
		}
	}
	
	/**
	 * 合并两个有序链表
	 * @时间复杂度 O(n/2) = O(n)
	 * @param headNode
	 * @return
	 */
	public SinglyNode<Integer> merge(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){
		SinglyNode<Integer> result = null;
		
		if(headNode1 == null) return headNode2;
		if(headNode2 == null) return headNode1;
		
		if(headNode1.getData() <= headNode2.getData()){
			result = headNode1;
			result.setNext(merge(headNode1.getNext(),headNode2));
		}else{
			result = headNode2;
			result.setNext(merge(headNode1,headNode2.getNext()));
		}
		return (SinglyNode<Integer>) result;
	}
	
	/**
	 * 非递归合并两个有序链表
	 * @param headNode1
	 * @param headNode2
	 * @return
	 */
	private SinglyNode<Integer> mergeNoRecursion(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){
		SinglyNode<Integer> result,currentNode;
		result = new SinglyNode<Integer>(null);
		currentNode = result;
		
		while (headNode1 != null && headNode2 != null) {
			if(headNode1.getData().intValue() <= headNode2.getData().intValue()){
				currentNode.setNext(headNode1);
				headNode1 = headNode1.getNext();
			}else{
				currentNode.setNext(headNode2);
				headNode2 = headNode2.getNext();
			}
			currentNode = currentNode.getNext();
		}
		
		if(headNode1 == null){
			currentNode.setNext(headNode2);
		}else{
			currentNode.setNext(headNode1);
		}
		
		return result.getNext();
	}
	
	/**
	 * 归并排序
	 * @时间复杂度 O(nlogn)
	 * @param headNode
	 * @return
	 */
	public SinglyNode<Integer> mergeSort(SinglyNode<Integer> headNode){
		if(headNode == null || headNode.getNext() == null){
			return headNode;
		}
		
		SinglyNode<Integer> middleNode = findMiddle(headNode);
		SinglyNode<Integer> halfHeadNode = middleNode.getNext();
		middleNode.setNext(null);
		
		return merge(mergeSort(headNode), mergeSort(halfHeadNode));
	}
	
	@Test
	public void testMethods(){
		SinglyNode<Integer> headNode = new SinglyNode<Integer>(1);		
		SinglyNode<Integer> tmpNode1 = new SinglyNode<Integer>(3);
		SinglyNode<Integer> tmpNode2 = new SinglyNode<Integer>(5);
		SinglyNode<Integer> tmpNode3 = new SinglyNode<Integer>(6);
		SinglyNode<Integer> tmpNode4 = new SinglyNode<Integer>(4);
		SinglyNode<Integer> tmpNode5 = new SinglyNode<Integer>(2);
		
		
		headNode.setNext(tmpNode1);
		tmpNode1.setNext(tmpNode2);
		tmpNode2.setNext(tmpNode3);
		tmpNode3.setNext(tmpNode4);
		tmpNode4.setNext(tmpNode5);
		
		System.out.println("排序之前：");
		print(headNode);
		
		headNode = mergeSort(headNode);
		System.out.println("排序之后： ");
		print(headNode);
		
	}

}
